package com.arithmetic;

/**
 * 二分查找算法
 */
public class BinarySearchTest {
    public static void main(String[] args) {
        /**
         *   给定一个个元素有序的（升序）整型数组 nums
         *   和一个目标值 target
         *   写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
         *   示例：
         *   输入: nums = [-1,0,3,5,9,12], target = 9
         *   输出: 4
         *   解释: 9 出现在 nums 中并且下标为 4
         */
        Integer[] nums = {-1,0,3,5,9,12,15,18,21,33,35,37};
        Integer target = 9;
        Boolean status = false;

        //获取自1970年1月1日 00：00：00 000到当前系统时间的总毫秒数。
        long nowTime = System.currentTimeMillis();
        System.out.println(nowTime);

        //统计一个方法耗费的时间
        //调用方法之前记录下毫秒数
        long begin = System.currentTimeMillis();

        //暴力破解
//        bruttForceAttack(nums,target,status);
        //二分算法
        Integer integer = binarySearch(nums, target, status);
        System.out.println(integer);

        //调用方法之后记录下毫秒数
        long end = System.currentTimeMillis();
        System.out.println("方法运行时间为：" + (end - begin) + "毫秒");//方法运行时间为：2毫秒

    }



    /**
     * 暴力破解查找算法
     * @param nums
     * @param target
     * @param status
     */
    private static void bruttForceAttack(Integer[] nums, Integer target, Boolean status){
        for (Integer i = 0; i < nums.length; i++) {
            if(target.equals(nums[i])){
                System.out.println("下标为："+i+"的值为"+target);
                status = true;
            }
        }
        if(!status){
            System.out.println("不存在的"+target+"值");
        }
    }

    /**
     * 二分查找唯一下标算法
     * @param nums
     * @param target
     * @param status
     */
    private static Integer binarySearch(Integer[] nums, Integer target, Boolean status) {
        //初始化最左侧的下标
        Integer left = 0;
        //确认最右侧的下标
        Integer right = nums.length;
        //如果右侧下标小于最左侧下标时,停止循环
        while (left < right) {
            //通过
            // 左侧下标值 + (右侧下标值减去左侧下标志 并通过“二进制右移”)
            // 获取当前数组二分之一的下标
            int mid = left + ((right - left) >> 1);
            //如果数组的下标值与 取值相等,返回值
            if (nums[mid].equals(target)) {
                return mid;
            //如果取到的值小于 目标值,说明不在该范围内,对左半部分进行下标赋值
            } else if (nums[mid] < target) {
                left = mid + 1;
            //如果取到的值 大于 目标值，说明该值区间为 目前的左侧下标值 至 目前的右侧下标值 区间
            } else if (nums[mid] > target) {
                right = mid;
            }
        }
        return -1;
    }
}
